OCaml 力をチェックするための問題

エクササイズ1

code:ocaml

# let rec f x = if x = 0 then x else false;;

Error: This expression has type bool but an expression was expected of type int

関数 f x は bool を返す関数なのだが、x = 0 は int を仮定しているため問題がある。

エクササイズ2

code:ocaml

# let rec f n = if n = 1 then 1 else n + f (n - 1);;

val f : int -> int = <fun>

# f 10;;

- : int = 55

エクササイズ3

(1) 各ノードにint型の値を保持する二分木を表すユーザー定義型 bt を、ヴァリアント型を用いて定義せよ

分からん...

これを読んで理解しよう

例

https://gyazo.com/74ae7a3fe36d0ca3ed16fa60daea0fed

ユーザー定義型

code:ocaml

type bt = Leaf | Branch of {left: bt; value: int; right: bt};;

let n1 = Branch {left = Leaf; value = 1; right = Leaf};;

let n5 = Branch {left = Leaf; value = 5; right = Leaf};;

let n13 = Branch {left = Leaf; value = 13; right = Leaf};;

let n55 = Branch {left = Leaf; value = 55; right = Leaf};;

let n3 = Branch {left = Leaf; value = 3; right = n5};;

let n34 = Branch {left = Leaf; value = 34; right = n55};;

let n2 = Branch {left = n1; value = 2; right = n3};;

let n21 = Branch {left = n13; value = 21; right = n34};;

let n8 = Branch {left = n2; value = 8; right = n21};;

code:ocaml

(2) bt型のtを受け取り、tの中に現れる全ての値の和を求める関数sumtreeを書け

code:ocaml

let rec sumtree bt =

match bt with

Leaf -> 0

| Branch {left = l; value = v; right = r} -> (sumtree l) + v + (sumtree r)

;;

(* 試してみる *)

# sumtree Leaf;;

- : int = 0

# sumtree n1;;

- : int = 1

# sumtree n3;;

- : int = 8

# sumtree n2;;

- : int = 11

# sumtree n34;;

- : int = 89

# sumtree n21;;

- : int = 123

# sumtree n8;;

- : int = 142

# 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 + 55;;

- : int = 142

(3) int -> int型の関数fとbt型の値tとを受け取り，t中に現れるすべての値にfを適用して得られる木を求める関数mapTreeを書け

code:ocaml

let rec mapTree f bt = match bt with Leaf -> Leaf | Branch {left = l; value = v; right = r} -> Branch {left = (mapTree f l); value = (f v); right = (mapTree f r)};;

(* 試してみる *)

# mapTree (fun x -> x * x) Leaf;;

- : bt = Leaf

# mapTree (fun x -> x * x) n1;;

- : bt = Branch {left = Leaf; value = 1; right = Leaf}

# mapTree (fun x -> x * x) n5;;

- : bt = Branch {left = Leaf; value = 25; right = Leaf}

# mapTree (fun x -> x * x) n3;;

- : bt =

Branch

{left = Leaf; value = 9;

right = Branch {left = Leaf; value = 25; right = Leaf}}

# mapTree (fun x -> x * x) n2;;

- : bt =

Branch

{left = Branch {left = Leaf; value = 1; right = Leaf}; value = 4;

right =

Branch

{left = Leaf; value = 9;

right = Branch {left = Leaf; value = 25; right = Leaf}}}

# mapTree (fun x -> x * x) n8;;

- : bt =

Branch

{left =

Branch

{left = Branch {left = Leaf; value = 1; right = Leaf}; value = 4;

right =

Branch

{left = Leaf; value = 9;

right = Branch {left = Leaf; value = 25; right = Leaf}}};

value = 64;

right =

Branch

{left = Branch {left = Leaf; value = 169; right = Leaf}; value = 441;

right =

Branch

{left = Leaf; value = 1156;

right = Branch {left = Leaf; value = 3025; right = Leaf}}}}